package com.song.boot.springstudy.sort.str;

import java.util.ArrayList;
import java.util.List;

public class RabinKarp {
    // 选择一个较大的质数作为哈希计算的基数
    private static final int BASE = 911382629;
    // 选择一个较大的质数作为模，减少哈希冲突
    private static final int MOD = 1000000007;

    /**
     * 在文本中查找所有模式串出现的位置
     * @param text 文本串
     * @param pattern 模式串
     * @return 所有匹配位置的索引列表
     */
    public static List<Integer> search(String text, String pattern) {
        List<Integer> result = new ArrayList<>();
        int textLen = text.length();
        int patternLen = pattern.length();

        // 边界情况处理
        if (patternLen == 0 || textLen < patternLen) {
            return result;
        }

        // 计算模式串的哈希值
        long patternHash = computeHash(pattern, 0, patternLen - 1);
        
        // 计算文本中第一个窗口的哈希值
        long textHash = computeHash(text, 0, patternLen - 1);
        
        // 计算BASE^(patternLen-1) mod MOD，用于后续滑动窗口计算
        long power = 1;
        for (int i = 0; i < patternLen - 1; i++) {
            power = (power * BASE) % MOD;
        }

        // 滑动窗口查找匹配
        for (int i = 0; i <= textLen - patternLen; i++) {
            // 哈希值相等，进行字符级验证
            if (patternHash == textHash) {
                boolean match = true;
                for (int j = 0; j < patternLen; j++) {
                    if (text.charAt(i + j) != pattern.charAt(j)) {
                        match = false;
                        break;
                    }
                }
                if (match) {
                    result.add(i);
                }
            }

            // 计算下一个窗口的哈希值
            if (i < textLen - patternLen) {
                // 移除窗口最左侧字符的哈希值，加上新字符的哈希值
                textHash = ( (textHash - text.charAt(i) * power) * BASE + text.charAt(i + patternLen) ) % MOD;
                
                // 确保哈希值为正数
                if (textHash < 0) {
                    textHash += MOD;
                }
            }
        }

        return result;
    }

    /**
     * 计算字符串从start到end位置的哈希值
     */
    private static long computeHash(String str, int start, int end) {
        long hash = 0;
        for (int i = start; i <= end; i++) {
            hash = (hash * BASE + str.charAt(i)) % MOD;
        }
        return hash;
    }

    public static void main(String[] args) {
        // 实际例子：在文本中查找模式串"ab"
        String text = "abracadabra";
        String pattern = "ab";
        
        List<Integer> positions = search(text, pattern);
        
        System.out.println("文本: " + text);
        System.out.println("模式串: " + pattern);
        System.out.println("匹配位置: " + positions);
    }
}
